
/*冒泡排序*/
/*
 * min -> max
冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
function bubbleSort(array){
	for (var i = 0; i < array.length; i++){
		for (var j = 1, k = 0; j < array.length - i; j++, k++){
			if (array[k] > array[j]){
				var temp = array[j];
				array[j] = array[k];
				array[k] = temp;
			}
		}
	}
	return(array);
}

function bubbleSort(array) {
  return bubble(array, 0, array.length - 1)
}

function bubble(array, leftIndex, rightIndex) {
  let activeIndex
  if (array.length > 1) {
    activeIndex = compare(array, leftIndex, rightIndex)
    if (activeIndex > 0) {
      bubble(array, leftIndex, activeIndex)
    }
  }
  return array
}

function compare(array, leftIndex, rightIndex) {
  let i = leftIndex
  let j = leftIndex + 1

  while (i < rightIndex) {
    if (array[i] > array[j]) {
      swap(array, i, j)
    }
    i++
    j++
  }
  return rightIndex - 1
}

/* 交换函数 */
function swap(array, a, b) {
  [array[b], array[a]] = [array[a], array[b]]
}


/*快速排序*/
/*
 * min -> max
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 */
/* 执行函数 */
function quickSort(array) {
  return quick(array, 0, array.length - 1)
}

/* 主函数 */
function quick(array, left, right) {
  let index
  if (array.length > 1) {
    index = partition(array, left, right)
    if (left < index - 1) {
      quick(array, left, index - 1)
    }
    if (index < right) {
      quick(array, index, right)
    }
  }
  return array
}

/* 划分操作函数 */
function partition(array, left, right) {
  console.log(left, right, array.slice(left, right + 1))
  const pivot = array[Math.floor((right + left) / 2)]
  let i = left
  let j = right

  while (i < j) {
    while (compare(array[i], pivot) === -1 && i < j) {
      i++
    }
    while (compare(array[j], pivot) === 1 && i < j) {
      j--
    }
    if (i <= j) {
      swap(array, i, j)
      i++
      j--
    }
  }
  return i
}

/* 比较函数 */
function compare(a, b) {
  return a === b ? 0 : a < b ? -1 : 1
}

/* 原地交换函数 */
function swap(array, a, b) {
  [array[a], array[b]] = [array[b], array[a]]
}


/*插入排序*/
/*
 * min -> max
 数组分成两部分：
 第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
 而第二部分就只包含这一个元素（即待插入元素）。
 在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中*/
function insertSort(array){
	for (var i = 1; i < array.length; i++){
		var current = array[i];
		for (var j = 0; j < i; j++){
			if (array[i] < array[j]){
				for (var k = i; k > j; k--){
					array[k] = array[k-1];
				}
				array[j] = current;
			}
		}
	}
	return(array)
}

/*选择排序*/
/*
 * min -> max
 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，
 然后，再从剩余未排序元素中继续寻找最小元素，
 然后放到排序序列末尾。
 以此类推，直到所有元素均排序完毕。
 */
function choiceSort(array){
	for (var i = 0; i < array.length; i++){
		var register = i;
		for (var j = i + 1; j < array.length; j++){
			if (array[register] > array[j]){
				register = j;
			}
		}
		if (register !== i){
			var temp = array[register];
			array[register] = array[i];
			array[i] = temp;
		}
	}
	return(array)
}

window.onload = function (){
	var bubble_sort = document.getElementsByClassName('bubble_sort')[0];
	var fast_sort = document.getElementsByClassName('fast_sort')[0];
	var insert_sort = document.getElementsByClassName('insert_sort')[0];
	var choice_sort = document.getElementsByClassName('choice_sort')[0];
	
	bubble_sort.innerHTML = bubbleSort([89,2,45,100,34,676,56,23,68,234,1,68,90]);
	fast_sort.innerHTML = fastSort([89,2,45,100,34,676,56,23,68,234,1,68,90]);
	insert_sort.innerHTML = insertSort([89,2,45,100,34,676,56,23,68,234,1,68,90]);
	choice_sort.innerHTML = choiceSort([89,2,45,100,34,676,56,23,68,234,1,68,90]);
}
